package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/27 15:16
 */
public class C977 {


    public static int[] sortedSquares(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }

    public static int[] sortedSquares2(int[] nums) {
        int m = -1;
        int[] ans = new int[nums.length];
        for (int i = 0; i < ans.length; i++) {
            if (nums[i] < 0) m = i;
            ans[i] = nums[i] * nums[i];
        }
        merge(ans, m, nums.length);
        return ans;
    }

    private static void merge(int[] arr, int m, int N) {
        int i = m, j = m + 1, helpIndex = 0;
        int[] help = new int[N];
        while (i >= 0 && j < N) {
            help[helpIndex++] = arr[i] <= arr[j] ? arr[i--] : arr[j++];
        }
        while (i >= 0) {
            help[helpIndex++] = arr[i--];
        }
        while (j < N) {
            help[helpIndex++] = arr[j++];
        }
        System.arraycopy(help, 0, arr, 0, arr.length);
    }


    // for test
    public static void main(String[] args) {
        int[] arr = {-1};
        System.out.println(Arrays.toString(sortedSquares2(arr)));
    }


}
